|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 力 ： [ちから, りょく] 1. (n-suf) strength 2. power ・ 力学 ： [りきがく] 【名詞】 1. mechanics 2. dynamics ・ 学 ： [がく] 【名詞】 1. learning 2. scholarship 3. erudition 4. knowledge ・ ラフ ： [らふ] 1. (adj,n) rough 2. (adj,n) rough ・ 描画 ： [びょうが] 1. (n,vs) drawing 2. painting ・ 画 ： [かく, が] 【名詞】 1. stroke
力学モデルによるグラフ描画（力指向アルゴリズム）は、グラフを美しく描画するためのアルゴリズムの一つである。 このアルゴリズムは、グラフのノードを2次元空間や3次元空間に配置して、辺の長さをほぼ等しい長さにし、グラフの辺ができるだけ交差しないようにすることを目的にしている。 このアルゴリズムでは、グラフの頂点と辺に仮想的な力を割り当て、力学的エネルギーの低い安定状態を探すことで、この目的を達成している。もっとも直截的なモデルでは、それぞれの辺をフックの法則にしたがうばねとみなし、それぞれの頂点をクーロンの法則にしたがう電荷をもつ粒子とみなす。 そして、その力学系の挙動をシミュレートし、弾性力や静電気力が粒子を近づけたり遠ざけたりするようすを計算する。粒子が安定な配置になり、位置が変化しなくなるまで、力の計算と粒子の移動を繰り返す。その時点で、グラフのレイアウトが完了し、描画される。この平衡状態は、すべての力が釣り合った状態に相当する。 ==長所== 以下が重要な長所である。 * 質の良い結果が得られる。少なくとも頂点が50-100ぐらいまでの中程度の大きさなら、 辺の長さが均一, 頂点の散らばり具合が均一、対称性があるという点について、たいていとても満足のいく結果となる。対称性はグラフの美しさの上でもっとも重要な点であり、他のアルゴリズムでは達成することが難しいものである。 * 柔軟性がある。このアルゴリズムは、追加の美学的基準に対応するように簡単に適用/拡張できる。実際に拡張された例としては、有向グラフへの対応、 3Dのグラフ描画、クラスタ化したグラフ描画、制約付きのグラフ描画、動的なグラフ描画などがある。 * 直感的である。バネ、といった身近なものの物理的なアナロジーに基づいているので、結果を予測したり、理解するのが簡単である。これは他のアルゴリズムにはない特徴である。 * シンプルである。典型的なアルゴリズムはシンプルであり、ちょっとした行数のコードで実装できる。他の種類のアルゴリズムである、orthogonalアルゴリズムのような方法ではより複雑になる。 * 操作しやすい。 力学的なアルゴリズムでは、操作しやすい特徴がある。グラフ描画の過程を、複雑に絡み合ったグラフがシンプルな配置に整理されていく様子を見ることで理解することができる。 いくつかの対話的なグラフ描画ツールでは、ユーザがノードを引っ張ることができ、それが平衡状態にもどる様子を見ることができる。これらは、動的なグラフ描画システムや、オンラインアルゴリズムを用いる場合に有用である。 * 強い理論的な基盤がある。 この項目で実装例として紹介しているような、シンプルだがアドホックなアルゴリズムは文章や実用においてよく現れていたが、それと同時に、より合理的なアプローチが注目されるようになった。 統計学では1930年代から似たような問題をmultidimensional scaling (MDS) で解いていたし、物理学には多体問題 に関連した研究については長い歴史を持っている。このことから、このような問題に対しては極めて成熟したアプローチをもっている。 一例として、metric MDS に対する stress majorization法は、以上で説明したグラフ描画に応用できる。 この方法で一様収束することが証明されている〔de Leeuw, J. (1988)〕。一様収束は、配置が必ず最終的に極小に到達し、停止することを保証するので重要である。減衰による方法（以下の擬似コードでの実装例のような場合）は、アルゴリズムは停止するが、真の極小に到達したことを保証するものではない。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「力学モデル (グラフ描画アルゴリズム)」の詳細全文を読む スポンサード リンク
|